/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / web / Is_Bidirected.web

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 75 68 72 | 69 67 40 6d 70 69 2d 73 |From uhr|ig@mpi-s|
|00000010| 62 2e 6d 70 67 2e 64 65 | 20 54 75 65 20 4f 63 74 |b.mpg.de| Tue Oct|
|00000020| 20 31 32 20 31 34 3a 33 | 33 3a 34 30 20 31 39 39 | 12 14:3|3:40 199|
|00000030| 33 0a 54 6f 3a 20 73 74 | 65 66 61 6e 0a 43 6f 6e |3.To: st|efan.Con|
|00000040| 74 65 6e 74 2d 4c 65 6e | 67 74 68 3a 20 33 32 30 |tent-Len|gth: 320|
|00000050| 32 0a 58 2d 4c 69 6e 65 | 73 3a 20 31 33 30 0a 0a |2.X-Line|s: 130..|
|00000060| 5c 64 6f 63 75 6d 65 6e | 74 73 74 79 6c 65 5b 31 |\documen|tstyle[1|
|00000070| 31 70 74 2c 63 6f 6d 6d | 65 6e 74 73 5d 7b 63 77 |1pt,comm|ents]{cw|
|00000080| 65 62 7d 0a 0a 5c 74 65 | 78 74 77 69 64 74 68 3d |eb}..\te|xtwidth=|
|00000090| 36 2e 35 69 6e 0a 5c 74 | 65 78 74 68 65 69 67 68 |6.5in.\t|extheigh|
|000000a0| 74 3d 39 69 6e 0a 5c 6f | 64 64 73 69 64 65 6d 61 |t=9in.\o|ddsidema|
|000000b0| 72 67 69 6e 3d 30 69 6e | 0a 5c 74 6f 70 6d 61 72 |rgin=0in|.\topmar|
|000000c0| 67 69 6e 3d 30 69 6e 0a | 0a 5c 62 65 67 69 6e 7b |gin=0in.|.\begin{|
|000000d0| 64 6f 63 75 6d 65 6e 74 | 7d 0a 0a 5c 6d 61 72 6b |document|}..\mark|
|000000e0| 72 69 67 68 74 7b 5c 66 | 62 6f 78 7b 5c 70 72 6f |right{\f|box{\pro|
|000000f0| 74 65 63 74 5c 74 69 6e | 79 20 76 65 72 73 69 6f |tect\tin|y versio|
|00000100| 6e 20 6f 66 20 5c 74 6f | 64 61 79 7d 7d 0a 5c 70 |n of \to|day}}.\p|
|00000110| 61 67 65 73 74 79 6c 65 | 7b 6d 79 68 65 61 64 69 |agestyle|{myheadi|
|00000120| 6e 67 73 7d 0a 0a 40 2a | 20 54 65 73 74 69 6e 67 |ngs}..@*| Testing|
|00000130| 20 42 69 64 69 72 65 63 | 74 65 64 6e 65 73 73 2e | Bidirec|tedness.|
|00000140| 0a 0a 5c 6e 6f 69 6e 64 | 65 6e 74 20 4c 65 74 20 |..\noind|ent Let |
|00000150| 24 47 24 20 62 65 20 61 | 20 73 69 6d 70 6c 65 20 |$G$ be a| simple |
|00000160| 67 72 61 70 68 2e 20 57 | 65 20 74 65 73 74 20 77 |graph. W|e test w|
|00000170| 68 65 74 68 65 72 20 24 | 47 24 20 69 73 20 62 69 |hether $|G$ is bi|
|00000180| 64 69 72 65 63 74 65 64 | 0a 61 6e 64 20 28 69 66 |directed|.and (if|
|00000190| 20 72 65 71 75 69 72 65 | 64 29 20 61 6c 73 6f 20 | require|d) also |
|000001a0| 65 73 74 61 62 6c 69 73 | 68 20 74 68 65 20 63 6f |establis|h the co|
|000001b0| 72 72 65 73 70 6f 6e 64 | 65 6e 63 65 20 62 65 74 |rrespond|ence bet|
|000001c0| 77 65 65 6e 20 65 64 67 | 65 73 20 61 6e 64 0a 74 |ween edg|es and.t|
|000001d0| 68 65 69 72 20 72 65 76 | 65 72 73 61 6c 73 2e 20 |heir rev|ersals. |
|000001e0| 57 65 20 66 69 72 73 74 | 20 62 75 63 6b 65 74 2d |We first| bucket-|
|000001f0| 2d 73 6f 72 74 20 74 68 | 65 20 65 64 67 65 73 20 |-sort th|e edges |
|00000200| 61 63 63 6f 72 64 69 6e | 67 20 74 6f 20 74 68 65 |accordin|g to the|
|00000210| 69 72 0a 74 61 72 67 65 | 74 20 6e 6f 64 65 2c 20 |ir.targe|t node, |
|00000220| 74 68 65 6e 20 61 63 63 | 6f 72 64 69 6e 67 20 74 |then acc|ording t|
|00000230| 6f 20 74 68 65 69 72 20 | 73 6f 75 72 63 65 20 6e |o their |source n|
|00000240| 6f 64 65 2e 20 54 68 65 | 20 72 65 73 75 6c 74 20 |ode. The| result |
|00000250| 69 73 20 0a 6d 61 69 6e | 74 61 69 6e 65 64 20 69 |is .main|tained i|
|00000260| 6e 20 61 20 6c 69 73 74 | 2e 20 41 66 74 65 72 77 |n a list|. Afterw|
|00000270| 61 72 64 73 20 77 65 20 | 73 6f 72 74 20 74 68 65 |ards we |sort the|
|00000280| 20 65 64 67 65 73 20 61 | 67 61 69 6e 2c 20 62 75 | edges a|gain, bu|
|00000290| 74 20 66 69 72 73 74 20 | 0a 61 63 63 6f 72 64 69 |t first |.accordi|
|000002a0| 6e 67 20 74 6f 20 74 68 | 65 69 72 20 73 6f 75 72 |ng to th|eir sour|
|000002b0| 63 65 20 6e 6f 64 65 20 | 61 6e 64 20 74 68 65 6e |ce node |and then|
|000002c0| 20 61 63 63 6f 72 64 69 | 6e 67 20 74 6f 20 74 68 | accordi|ng to th|
|000002d0| 65 69 72 20 74 61 72 67 | 65 74 20 6e 6f 64 65 2e |eir targ|et node.|
|000002e0| 0a 54 68 65 20 72 65 73 | 75 6c 74 20 69 73 20 6d |.The res|ult is m|
|000002f0| 61 69 6e 74 61 69 6e 65 | 64 20 69 6e 20 61 20 73 |aintaine|d in a s|
|00000300| 65 63 6f 6e 64 20 6c 69 | 73 74 2e 20 53 69 6e 63 |econd li|st. Sinc|
|00000310| 65 20 7c 62 75 63 6b 65 | 74 20 73 6f 72 74 7c 20 |e |bucke|t sort| |
|00000320| 69 73 20 0a 73 74 61 62 | 6c 65 2c 0a 69 6e 20 61 |is .stab|le,.in a|
|00000330| 20 62 69 64 69 72 65 63 | 74 65 64 20 67 72 61 70 | bidirec|ted grap|
|00000340| 68 20 74 68 65 20 70 6f | 73 69 74 69 6f 6e 20 6f |h the po|sition o|
|00000350| 66 20 61 6e 20 65 64 67 | 65 20 69 6e 20 74 68 65 |f an edg|e in the|
|00000360| 20 66 69 72 73 74 20 6c | 69 73 74 0a 63 6f 72 72 | first l|ist.corr|
|00000370| 65 73 70 6f 6e 64 73 20 | 74 6f 20 74 68 65 20 70 |esponds |to the p|
|00000380| 6f 73 69 74 69 6f 6e 20 | 6f 66 20 74 68 65 20 72 |osition |of the r|
|00000390| 65 76 65 72 73 61 6c 20 | 65 64 67 65 20 69 6e 20 |eversal |edge in |
|000003a0| 74 68 65 20 73 65 63 6f | 6e 64 0a 6c 69 73 74 2e |the seco|nd.list.|
|000003b0| 20 54 68 65 20 66 6f 6c | 6c 6f 77 69 6e 67 20 70 | The fol|lowing p|
|000003c0| 72 6f 63 65 64 75 72 65 | 20 0a 63 68 65 63 6b 73 |rocedure| .checks|
|000003d0| 20 74 68 69 73 20 72 65 | 6c 61 74 69 6f 6e 2e 20 | this re|lation. |
|000003e0| 0a 41 73 20 73 6f 6f 6e | 20 61 73 20 74 68 65 20 |.As soon| as the |
|000003f0| 74 65 73 74 65 64 20 65 | 64 67 65 73 20 64 6f 20 |tested e|dges do |
|00000400| 6e 6f 74 20 63 6f 72 72 | 65 73 70 6f 6e 64 2c 20 |not corr|espond, |
|00000410| 66 61 6c 73 65 20 69 73 | 20 72 65 74 75 72 6e 65 |false is| returne|
|00000420| 64 2e 20 0a 0a 40 63 0a | 62 6f 6f 6c 20 69 73 5f |d. ..@c.|bool is_|
|00000430| 62 69 64 69 72 65 63 74 | 65 64 28 63 6f 6e 73 74 |bidirect|ed(const|
|00000440| 20 67 72 61 70 68 26 20 | 47 29 20 20 20 20 20 0a | graph& |G)     .|
|00000450| 7b 0a 20 2f 2f 20 63 6f | 6d 70 75 74 65 73 20 66 |{. // co|mputes f|
|00000460| 6f 72 20 65 76 65 72 79 | 20 65 64 67 65 20 65 20 |or every| edge e |
|00000470| 3d 20 28 76 2c 77 29 20 | 69 6e 20 47 20 69 74 73 |= (v,w) |in G its|
|00000480| 20 72 65 76 65 72 73 61 | 6c 20 72 65 76 65 72 73 | reversa|l revers|
|00000490| 61 6c 5b 65 5d 20 3d 20 | 28 77 2c 76 29 0a 20 2f |al[e] = |(w,v). /|
|000004a0| 2f 20 69 6e 20 47 20 28 | 20 6e 69 6c 20 69 66 20 |/ in G (| nil if |
|000004b0| 6e 6f 74 20 70 72 65 73 | 65 6e 74 29 2e 20 52 65 |not pres|ent). Re|
|000004c0| 74 75 72 6e 73 20 74 72 | 75 65 20 69 66 20 65 76 |turns tr|ue if ev|
|000004d0| 65 72 79 20 65 64 67 65 | 20 68 61 73 20 61 0a 20 |ery edge| has a. |
|000004e0| 2f 2f 20 72 65 76 65 72 | 73 61 6c 20 61 6e 64 20 |// rever|sal and |
|000004f0| 66 61 6c 73 65 20 6f 74 | 68 65 72 77 69 73 65 2e |false ot|herwise.|
|00000500| 0a 0a 20 20 69 6e 74 20 | 6e 20 3d 20 47 2e 6d 61 |..  int |n = G.ma|
|00000510| 78 5f 69 5f 6e 6f 64 65 | 28 29 3b 0a 20 20 69 6e |x_i_node|();.  in|
|00000520| 74 20 63 6f 75 6e 74 20 | 3d 20 30 3b 0a 0a 20 20 |t count |= 0;..  |
|00000530| 65 64 67 65 20 65 2c 72 | 3b 0a 0a 20 20 6c 69 73 |edge e,r|;..  lis|
|00000540| 74 3c 65 64 67 65 3e 20 | 45 6c 20 3d 20 47 2e 61 |t<edge> |El = G.a|
|00000550| 6c 6c 5f 65 64 67 65 73 | 28 29 3b 0a 20 20 45 6c |ll_edges|();.  El|
|00000560| 2e 62 75 63 6b 65 74 5f | 73 6f 72 74 28 30 2c 6e |.bucket_|sort(0,n|
|00000570| 2c 26 65 64 67 65 5f 6f | 72 64 32 29 3b 0a 20 20 |,&edge_o|rd2);.  |
|00000580| 45 6c 2e 62 75 63 6b 65 | 74 5f 73 6f 72 74 28 30 |El.bucke|t_sort(0|
|00000590| 2c 6e 2c 26 65 64 67 65 | 5f 6f 72 64 31 29 3b 0a |,n,&edge|_ord1);.|
|000005a0| 20 20 0a 20 20 6c 69 73 | 74 3c 65 64 67 65 3e 20 |  .  lis|t<edge> |
|000005b0| 45 6c 31 20 3d 20 47 2e | 61 6c 6c 5f 65 64 67 65 |El1 = G.|all_edge|
|000005c0| 73 28 29 3b 0a 20 20 45 | 6c 31 2e 62 75 63 6b 65 |s();.  E|l1.bucke|
|000005d0| 74 5f 73 6f 72 74 28 30 | 2c 6e 2c 26 65 64 67 65 |t_sort(0|,n,&edge|
|000005e0| 5f 6f 72 64 31 29 3b 0a | 20 20 45 6c 31 2e 62 75 |_ord1);.|  El1.bu|
|000005f0| 63 6b 65 74 5f 73 6f 72 | 74 28 30 2c 6e 2c 26 65 |cket_sor|t(0,n,&e|
|00000600| 64 67 65 5f 6f 72 64 32 | 29 3b 0a 0a 0a 20 20 2f |dge_ord2|);...  /|
|00000610| 2f 20 6d 65 72 67 65 20 | 45 6c 20 61 6e 64 20 45 |/ merge |El and E|
|00000620| 6c 31 20 74 6f 20 66 69 | 6e 64 20 63 6f 72 72 65 |l1 to fi|nd corre|
|00000630| 73 70 6f 6e 64 69 6e 67 | 20 65 64 67 65 73 0a 0a |sponding| edges..|
|00000640| 20 20 77 68 69 6c 65 20 | 28 21 20 45 6c 2e 65 6d |  while |(! El.em|
|00000650| 70 74 79 28 29 20 26 26 | 20 21 20 45 6c 31 2e 65 |pty() &&| ! El1.e|
|00000660| 6d 70 74 79 28 29 29 0a | 20 20 7b 20 65 20 3d 20 |mpty()).|  { e = |
|00000670| 45 6c 2e 68 65 61 64 28 | 29 3b 0a 20 20 20 20 72 |El.head(|);.    r|
|00000680| 20 3d 20 45 6c 31 2e 68 | 65 61 64 28 29 3b 0a 0a | = El1.h|ead();..|
|00000690| 20 20 20 20 69 66 20 28 | 28 74 61 72 67 65 74 28 |    if (|(target(|
|000006a0| 72 29 20 3d 3d 20 73 6f | 75 72 63 65 28 65 29 29 |r) == so|urce(e))|
|000006b0| 26 26 28 73 6f 75 72 63 | 65 28 72 29 20 3d 3d 20 |&&(sourc|e(r) == |
|000006c0| 74 61 72 67 65 74 28 65 | 29 29 29 20 0a 20 20 20 |target(e|))) .   |
|000006d0| 20 20 20 20 20 20 7b 20 | 45 6c 31 2e 70 6f 70 28 |      { |El1.pop(|
|000006e0| 29 3b 0a 20 20 20 20 20 | 20 20 20 20 20 20 45 6c |);.     |      El|
|000006f0| 2e 70 6f 70 28 29 3b 0a | 20 20 20 20 20 20 20 20 |.pop();.|        |
|00000700| 20 20 7d 0a 20 20 20 20 | 65 6c 73 65 0a 20 20 20 |  }.    |else.   |
|00000710| 20 20 20 20 20 20 72 65 | 74 75 72 6e 20 66 61 6c |      re|turn fal|
|00000720| 73 65 3b 0a 20 20 7d 0a | 20 20 72 65 74 75 72 6e |se;.  }.|  return|
|00000730| 20 74 72 75 65 3b 0a 0a | 7d 0a 0a 40 20 54 68 65 | true;..|}..@ The|
|00000740| 20 66 6f 6c 6c 6f 77 69 | 6e 67 20 70 72 6f 63 65 | followi|ng proce|
|00000750| 64 75 72 65 20 0a 61 6c | 73 6f 20 65 73 74 61 62 |dure .al|so estab|
|00000760| 6c 69 73 68 65 73 20 74 | 68 65 20 63 6f 72 72 65 |lishes t|he corre|
|00000770| 73 70 6f 6e 64 65 6e 63 | 65 20 62 65 74 77 65 65 |spondenc|e betwee|
|00000780| 6e 20 65 64 67 65 73 20 | 61 6e 64 20 74 68 65 69 |n edges |and thei|
|00000790| 72 20 72 65 76 65 72 73 | 61 6c 73 2e 0a 46 6f 72 |r revers|als..For|
|000007a0| 20 65 76 65 72 79 20 65 | 64 67 65 20 7c 65 20 3d | every e|dge |e =|
|000007b0| 20 28 76 2c 20 77 29 7c | 20 69 6e 20 24 47 24 20 | (v, w)|| in $G$ |
|000007c0| 69 74 20 63 6f 6d 70 75 | 74 65 73 20 69 74 73 20 |it compu|tes its |
|000007d0| 72 65 76 65 72 73 61 6c | 0a 7c 72 65 76 65 72 73 |reversal|.|revers|
|000007e0| 61 6c 5b 65 5d 20 3d 20 | 28 77 2c 76 29 7c 20 69 |al[e] = |(w,v)| i|
|000007f0| 66 20 65 78 69 73 74 69 | 6e 67 20 69 6e 20 24 47 |f existi|ng in $G|
|00000800| 24 20 28 7c 6e 69 6c 7c | 20 6f 74 68 65 72 77 69 |$ (|nil|| otherwi|
|00000810| 73 65 29 2e 20 49 66 20 | 65 76 65 72 79 0a 65 64 |se). If |every.ed|
|00000820| 67 65 20 68 61 73 20 61 | 20 72 65 76 65 72 73 61 |ge has a| reversa|
|00000830| 6c 20 69 74 20 72 65 74 | 75 72 6e 73 20 7c 74 72 |l it ret|urns |tr|
|00000840| 75 65 7c 20 61 6e 64 20 | 7c 66 61 6c 73 65 7c 20 |ue| and ||false| |
|00000850| 6f 74 68 65 72 77 69 73 | 65 2e 0a 0a 0a 40 63 0a |otherwis|e....@c.|
|00000860| 0a 62 6f 6f 6c 20 69 73 | 5f 62 69 64 69 72 65 63 |.bool is|_bidirec|
|00000870| 74 65 64 28 63 6f 6e 73 | 74 20 67 72 61 70 68 26 |ted(cons|t graph&|
|00000880| 20 47 2c 20 65 64 67 65 | 5f 61 72 72 61 79 3c 65 | G, edge|_array<e|
|00000890| 64 67 65 3e 26 20 72 65 | 76 65 72 73 61 6c 29 20 |dge>& re|versal) |
|000008a0| 20 20 20 20 0a 7b 0a 20 | 2f 2f 20 63 6f 6d 70 75 |    .{. |// compu|
|000008b0| 74 65 73 20 66 6f 72 20 | 65 76 65 72 79 20 65 64 |tes for |every ed|
|000008c0| 67 65 20 65 20 3d 20 28 | 76 2c 77 29 20 69 6e 20 |ge e = (|v,w) in |
|000008d0| 47 20 69 74 73 20 72 65 | 76 65 72 73 61 6c 20 72 |G its re|versal r|
|000008e0| 65 76 65 72 73 61 6c 5b | 65 5d 20 3d 20 28 77 2c |eversal[|e] = (w,|
|000008f0| 76 29 0a 20 2f 2f 20 69 | 6e 20 47 20 28 20 6e 69 |v). // i|n G ( ni|
|00000900| 6c 20 69 66 20 6e 6f 74 | 20 70 72 65 73 65 6e 74 |l if not| present|
|00000910| 29 2e 20 52 65 74 75 72 | 6e 73 20 74 72 75 65 20 |). Retur|ns true |
|00000920| 69 66 20 65 76 65 72 79 | 20 65 64 67 65 20 68 61 |if every| edge ha|
|00000930| 73 20 61 0a 20 2f 2f 20 | 72 65 76 65 72 73 61 6c |s a. // |reversal|
|00000940| 20 61 6e 64 20 66 61 6c | 73 65 20 6f 74 68 65 72 | and fal|se other|
|00000950| 77 69 73 65 2e 0a 0a 20 | 20 69 6e 74 20 6e 20 3d |wise... | int n =|
|00000960| 20 47 2e 6d 61 78 5f 69 | 5f 6e 6f 64 65 28 29 3b | G.max_i|_node();|
|00000970| 0a 20 20 69 6e 74 20 63 | 6f 75 6e 74 20 3d 20 30 |.  int c|ount = 0|
|00000980| 3b 0a 0a 20 20 65 64 67 | 65 20 65 2c 72 3b 0a 0a |;..  edg|e e,r;..|
|00000990| 20 20 66 6f 72 61 6c 6c | 5f 65 64 67 65 73 28 65 |  forall|_edges(e|
|000009a0| 2c 47 29 20 72 65 76 65 | 72 73 61 6c 5b 65 5d 20 |,G) reve|rsal[e] |
|000009b0| 3d 20 30 3b 0a 0a 20 20 | 6c 69 73 74 3c 65 64 67 |= 0;..  |list<edg|
|000009c0| 65 3e 20 45 6c 20 3d 20 | 47 2e 61 6c 6c 5f 65 64 |e> El = |G.all_ed|
|000009d0| 67 65 73 28 29 3b 0a 20 | 20 45 6c 2e 62 75 63 6b |ges();. | El.buck|
|000009e0| 65 74 5f 73 6f 72 74 28 | 30 2c 6e 2c 26 65 64 67 |et_sort(|0,n,&edg|
|000009f0| 65 5f 6f 72 64 32 29 3b | 0a 20 20 45 6c 2e 62 75 |e_ord2);|.  El.bu|
|00000a00| 63 6b 65 74 5f 73 6f 72 | 74 28 30 2c 6e 2c 26 65 |cket_sor|t(0,n,&e|
|00000a10| 64 67 65 5f 6f 72 64 31 | 29 3b 0a 20 20 0a 20 20 |dge_ord1|);.  .  |
|00000a20| 6c 69 73 74 3c 65 64 67 | 65 3e 20 45 6c 31 20 3d |list<edg|e> El1 =|
|00000a30| 20 47 2e 61 6c 6c 5f 65 | 64 67 65 73 28 29 3b 0a | G.all_e|dges();.|
|00000a40| 20 20 45 6c 31 2e 62 75 | 63 6b 65 74 5f 73 6f 72 |  El1.bu|cket_sor|
|00000a50| 74 28 30 2c 6e 2c 26 65 | 64 67 65 5f 6f 72 64 31 |t(0,n,&e|dge_ord1|
|00000a60| 29 3b 0a 20 20 45 6c 31 | 2e 62 75 63 6b 65 74 5f |);.  El1|.bucket_|
|00000a70| 73 6f 72 74 28 30 2c 6e | 2c 26 65 64 67 65 5f 6f |sort(0,n|,&edge_o|
|00000a80| 72 64 32 29 3b 0a 0a 0a | 20 20 2f 2f 20 6d 65 72 |rd2);...|  // mer|
|00000a90| 67 65 20 45 6c 20 61 6e | 64 20 45 6c 31 20 74 6f |ge El an|d El1 to|
|00000aa0| 20 66 69 6e 64 20 63 6f | 72 72 65 73 70 6f 6e 64 | find co|rrespond|
|00000ab0| 69 6e 67 20 65 64 67 65 | 73 0a 0a 20 20 77 68 69 |ing edge|s..  whi|
|00000ac0| 6c 65 20 28 21 20 45 6c | 2e 65 6d 70 74 79 28 29 |le (! El|.empty()|
|00000ad0| 20 26 26 20 21 20 45 6c | 31 2e 65 6d 70 74 79 28 | && ! El|1.empty(|
|00000ae0| 29 29 0a 20 20 7b 20 65 | 20 3d 20 45 6c 2e 68 65 |)).  { e| = El.he|
|00000af0| 61 64 28 29 3b 0a 20 20 | 20 20 72 20 3d 20 45 6c |ad();.  |  r = El|
|00000b00| 31 2e 68 65 61 64 28 29 | 3b 0a 0a 0a 20 20 20 20 |1.head()|;...    |
|00000b10| 69 66 20 28 74 61 72 67 | 65 74 28 72 29 20 3d 3d |if (targ|et(r) ==|
|00000b20| 20 73 6f 75 72 63 65 28 | 65 29 29 0a 20 20 20 20 | source(|e)).    |
|00000b30| 20 20 69 66 20 28 73 6f | 75 72 63 65 28 72 29 20 |  if (so|urce(r) |
|00000b40| 3d 3d 20 74 61 72 67 65 | 74 28 65 29 29 0a 20 20 |== targe|t(e)).  |
|00000b50| 20 20 20 20 20 20 20 7b | 20 72 65 76 65 72 73 61 |       {| reversa|
|00000b60| 6c 5b 65 5d 20 3d 20 72 | 3b 0a 20 20 20 20 20 20 |l[e] = r|;.      |
|00000b70| 20 20 20 20 20 45 6c 31 | 2e 70 6f 70 28 29 3b 0a |     El1|.pop();.|
|00000b80| 20 20 20 20 20 20 20 20 | 20 20 20 45 6c 2e 70 6f |        |   El.po|
|00000b90| 70 28 29 3b 0a 20 20 20 | 20 20 20 20 20 20 20 20 |p();.   |        |
|00000ba0| 63 6f 75 6e 74 2b 2b 3b | 0a 20 20 20 20 20 20 20 |count++;|.       |
|00000bb0| 20 20 20 7d 0a 20 20 20 | 20 20 20 65 6c 73 65 0a |   }.   |   else.|
|00000bc0| 20 20 20 20 20 20 20 20 | 20 69 66 20 28 69 6e 64 |        | if (ind|
|00000bd0| 65 78 28 73 6f 75 72 63 | 65 28 72 29 29 20 3c 20 |ex(sourc|e(r)) < |
|00000be0| 69 6e 64 65 78 28 74 61 | 72 67 65 74 28 65 29 29 |index(ta|rget(e))|
|00000bf0| 29 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 45 |).      |       E|
|00000c00| 6c 31 2e 70 6f 70 28 29 | 3b 0a 20 20 20 20 20 20 |l1.pop()|;.      |
|00000c10| 20 20 20 65 6c 73 65 0a | 20 20 20 20 20 20 20 20 |   else.|        |
|00000c20| 20 20 20 20 20 45 6c 2e | 70 6f 70 28 29 3b 0a 0a |     El.|pop();..|
|00000c30| 20 20 20 20 65 6c 73 65 | 0a 20 20 20 20 20 20 69 |    else|.      i|
|00000c40| 66 20 28 69 6e 64 65 78 | 28 74 61 72 67 65 74 28 |f (index|(target(|
|00000c50| 72 29 29 20 3c 20 69 6e | 64 65 78 28 73 6f 75 72 |r)) < in|dex(sour|
|00000c60| 63 65 28 65 29 29 29 0a | 20 20 20 20 20 20 20 20 |ce(e))).|        |
|00000c70| 20 20 45 6c 31 2e 70 6f | 70 28 29 3b 0a 20 20 20 |  El1.po|p();.   |
|00000c80| 20 20 20 65 6c 73 65 0a | 20 20 20 20 20 20 20 20 |   else.|        |
|00000c90| 20 20 45 6c 2e 70 6f 70 | 28 29 3b 0a 0a 20 20 20 |  El.pop|();..   |
|00000ca0| 20 7d 0a 20 20 72 65 74 | 75 72 6e 20 28 63 6f 75 | }.  ret|urn (cou|
|00000cb0| 6e 74 20 3d 3d 20 47 2e | 6e 75 6d 62 65 72 5f 6f |nt == G.|number_o|
|00000cc0| 66 5f 65 64 67 65 73 28 | 29 29 3b 0a 0a 7d 0a 20 |f_edges(|));..}. |
|00000cd0| 0a 40 0a 5c 65 6e 64 7b | 64 6f 63 75 6d 65 6e 74 |.@.\end{|document|
|00000ce0| 7d 0a 0a                |                         |}..     |        |
+--------+-------------------------+-------------------------+--------+--------+